1. Field of the Invention
The present invention relates to communication networks and, more particularly, to a method and apparatus for controlling the dissemination of routing information on a communication network.
2. Description of the Related Art
Data communication networks may include various computers, servers, nodes, routers, switches, bridges, hubs, proxies, and other network devices coupled to and configured to pass data to one another. These devices will be referred to herein as “network elements.” Data is communicated through the data communication network by passing protocol data units, such as Internet Protocol packets, Ethernet Frames, data cells, segments, or other logical associations of bits/bytes of data, between the network elements by utilizing one or more communication links between the devices. A particular protocol data unit may be handled by multiple network elements and cross multiple communication links as it travels between its source and its destination over the network.
There exists a class of networks in which traffic patterns are very focused. In particular, the traffic in these networks generally flows either from a well known focal point out to all the other nodes, or the reverse, from all those nodes back to the focal point. In these networks rarely, if ever, does traffic flow in any other pattern. One example of a network that generally exhibits these characteristics is a wireless ad-hoc network containing a network of wireless routers spanning a neighborhood and providing wireless access to individual users in the neighborhood, although the invention is not limited to an implementation in this particular type of network.
FIG. 1 illustrates a network 10 in which a focal point F 12 acts as an interface between a group of network elements (nodes) 14 interconnected in a mesh network configuration and an external network 16. In the following discussion, the focal nodes will be assumed to be access points to resources external to the network 16. For example, the focal nodes may contain a direct link to higher bandwidth resources of the Internet or the Public Switched Telephone Network (PSTN). Alternatively, the focal nodes may be a transmission point between a lower level mesh network interconnecting the nodes 14, and an upper level mesh interconnecting the focal points 12. The invention is not limited to this embodiment however.
The network elements 14 may be wireless access devices or other types of network elements. Within the mesh, the network elements are typically homogenous devices having approximately equal capacity. For example, the network elements may be wireless routers configured to transmit wireless signals using a particular protocol. Since the protocol defines the transmission bandwidth available over a given link between adjacent nodes, the network elements in this instance are practically limited to the protocol definition regardless of their physical capabilities.
Routing information on a network, such as the network illustrated in FIG. 1, may be exchanged using a variety of different protocols. Two classes of routing protocols include distance vector and link state routing protocols. The invention discussed below will be discussed in particular as applying to link state routing protocols. The invention is not limited in this regard, though, as it may also be applied to distance vector routing protocols.
Routing Information Protocol (RIP) is one example of a distance-vector routing protocol in which routers broadcast their entire current routing tables periodically, typically every 30 seconds. The messages contain lists of destination routers along with a distance to that destination measured in the number of hops to the destination. Optionally, other metrics may be used to measure the distance to the destination. In a large network, RIP may experience problems in that routing update messages propagate very slowly through the network and it may take a long time for the network to converge after a modification to the network, such as a link or node failure.
Link state routing protocols are different than distance vector protocols in that update messages are used to advertise routing information, but each router only advertises information about links to which it is connected. Update messages will be referred to herein as Link State Advertisements (LSAs). Link State routers maintain topology databases containing representations of every link and router in the network, and a state for each element. Examples of common link state routing protocols include Open Shortest Path First (OSPF) and Intermediate System to Intermediate System (IS-IS), although the invention is not limited to these example link state routing protocols.
Link state routing protocols, such as OSPF or IS-IS, work well in small networks. In a large network, however, with hundreds or thousands of routers and multiple times that many links, the overhead associated with exchanging LSAs may become prohibitive. Specifically, every time the state of one of the links in the network changes, a LSA will be flooded to every node on the network to ensure that every node on the network is able to update its link state table. Delays attendant with exchanging link-state messages, updating databases, and recalculating routes may cause topology convergence to be delayed on the network. Additionally, the larger the network the larger the link state database that must be created and maintained by the nodes on the network.
To alleviate this problem, the concept of OSPF areas was developed. OSPF areas are logical subdivisions of an OSPF network. OSPF routers within one area do not exchange topology updates with the routers in the other areas, to thereby limit the number of routers that are required to exchange LSAs. The logical partitioning is advantageous in that it limits the number of LSAs distributed on the network, limits the size of the link state databases maintained by the nodes, and accelerates topology convergence.
FIG. 2 illustrates a network 20 which has been partitioned into several OSPF areas 22. As shown in FIG. 2, each area contains a finite number of network elements 14. Link state advertisements, such as an advertisement relating to link Wi-Wk 24, may propagate within the area 22 but will not be advertised outside of that area.
Routers that sit on the border between adjacent OSPF areas are referred to as area border routers 26 or border gateways. In FIG. 2, the area border routers are colored solid black. Area border routers filter for topology updates and prevent LSAs from passing between domains. Area border routers maintain a topology database for both OSPF areas (or multiple topology databases where they sit on a border with more than 2 OSPF areas) to enable paths through the network to traverse the several OSPF areas. Area border routers communicate with each other using special link-state messages that contain a shorthand summary of the topologies of their respective areas.
In a wireless ad-hoc network, it may be difficult to define where the OSPF areas should be drawn. Specifically, one of the advantages of the ad-hoc nature of the network is that extensive planning does not need to take place. This is in direct contravention with the wisdom that has built up with defining OSPF areas and the careful planning that takes place in conventional OSPF networks.
Additionally, since most, if not all, of the network access points in an envisioned ad-hoc wireless network will be of relatively uniform capacity, designating one or more wireless network nodes as an area border router may cause artificial congestion in the network. Specifically, by designating a particular router as an area border router, all traffic that is to pass from one area to another is required to go through that area border router. Artificially concentrating traffic on one or a small number of routers presents a likely congestion problem at those router(s). While traffic engineering may be used to balance traffic on the various links leading to the area border router, it does not alleviate the congestion at that node.
Utilizing area border routers in an ad-hoc network with focal-node centric flow patterns is more troublesome. Specifically, where the vast majority of the traffic on a network is directed to or from a focal node, if that node is to fail, the traffic will need to be directed to another focal node. Where this traffic needs to traverse a border to find a focal node, all the traffic from the area may be required to pass through the area border router, which may further contribute to congestion in the area border router. While area border routers in conventional networks are conventionally of a higher capacity to handle the expected aggregate loads, this is difficult to do in an ad-hoc network with an intentional lack of centralized management and planning.
Defining areas in a network also introduces yet another problem, especially in ad-hoc networks. Specifically, whenever a network is defined to have areas, it becomes necessary to name the areas and tell the routers what area they belong to. In an ad-hoc network where a lack of centralized planning and management is one of the goals, requiring the nodes to be provisioned with area IDs makes deployment of the ad-hoc network more onerous. Additionally, where the nodes are mobile, keeping track of the node's location and its area IDs becomes even more difficult from a centralized management standpoint.